#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
https://blog.csdn.net/zdy_lsh/article/details/77842475

https://www.geeksforgeeks.org/shortest-un-ordered-subarray/

    从左到右: 记录最大值, 和当前值比较.
    从右到左: 记录最小值, 和当前值比较.

"""

class Solution:
    def __init__(self):
        pass

    def shortest_unordered_subarray(self, nums):

        left = len(nums)
        local_max = -1
        local_max_idx = -1

        for i in range(len(nums)):
            e = nums[i]
            if e > local_max:
                # 正常
                local_max_idx, local_max = i, e
            elif e == local_max:
                pass
            else:
                # 异常(非排序)
                left = local_max_idx
                break

        right = -1
        local_min = len(nums)
        local_min_idx = len(nums)
        for i in range(len(nums)-1, -1, -1):
            e = nums[i]
            if e < local_max:
                local_min_idx, local_min = i, e
            elif e == local_max:
                pass
            else:
                right = local_min_idx
                break

        return left, right

    def reverse_range(self, num):
        return range(num-1, -1, -1)



def test():
    s = Solution()
    nums = [7, 9, 10, 8, 11]

    left_idx, right_idx = s.shortest_unordered_subarray(nums)
    print(left_idx, right_idx, right_idx-left_idx+1)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
